package com.yinxin.wudasuanfa.dongtaiguihua;

/**
 *
 * @author yinxin
 * @version 1.0
 * @Description: 动态规划是对重复计算的结果做保存，最终减少计算时间。
 * 解题思路：问题抽象化、建立模型、寻找约束条件、判断是否满足最优性原理、找大问题与小问题的递推关系式、填表、寻找解组成
 * 01背包：
 * 假设你是⼩偷，背着只能装下四磅重东西的背包,你可以选择1磅1000美元的iphone，2磅2500美元的电吉他，3磅4500美元的⾳响，4磅6000美元的笔记本电脑
 * @date 2022/5/513:54
 */
public class Exercise1 {
    public static void main(String[] args) {
        int[]  weight= {2, 1, 3, 4};
        int[] value = {1000, 2500, 4500, 6000};
        backPack_01(value, weight);
    }
    //01背包
    private static void backPack_01(int[] value,int[] weight){
        int num=4;//物品索引
        int contain=6;//背包容量
        int[][] maxValue = new int[num+1][contain+1];//构造最优解的网格 int[y轴 物品编号][x轴 重量]
        for (int i = 1; i <= num; i++) {//物品号码和i同步，物品编号和i-同步
            for (int j = 1; j <= contain; j++) {//背包容纳重量和j同步，重量索引和j-1同步
                if(i==1){ //取第一件物品时只考虑能不能放下去
                    maxValue[i][j]=weight[i-1]<=j-1?value[i-1]:0;
                }else {
                    //取其他物品时：1、当前物品大于背包容量，则取不包含这个物品的上一个物品的同样重量下的最优解。即：
                    //2、当前物品小于等于当前背包容量，则比较不装这个物品时的最大值和 装上这个物品剩下容量下装之前物品的架子加上这个物品价值
                    maxValue[i][j]=j>=weight[i-1]?value[i-1]+maxValue[i-1][j-weight[i-1]]:maxValue[i-1][j];
                }
            }
        }
        for (int i = 0; i < maxValue.length; i++) {
            for (int j = 0; j < maxValue[i].length; j++) {
                System.out.print(maxValue[i][j]+"        ");
            }
            System.out.println();
        }
        System.out.println("最多能装价值"+maxValue[num-1][contain]+"的东西！");
    }
    //完全背包

}

/*if(i==0){
                    maxValue[i][j-1]=weight[i]<=j?value[i]:0;
                    //要初始化第⼀⾏，因为后⾯i要-1；如果当前的背包容量，能容纳当前⾏的物品重量，则为该物品的价值，反之为0
                }else {
                    int topValue = maxValue[i-1][j-1];//同一列上一个网格的值，代表在这个容量下面最优的总价值 weight[i]>j的情况
                    //System.out.print("topValue"+topValue);
                    //int thisValue = weight[i]<=j?(j>weight[i]?value[i]+maxValue[i-1][j-1-weight[i]]:value[i]):topValue;
                    int thisValue = j>weight[i]?value[i]+maxValue[i-1][j-1-weight[i]]:value[i];
                    //System.out.print("     thisValue:"+thisValue);
                    //thisValue为装上当前物品后，剩余背包容量且不包括装当前物品背包能装的最大价值+这个物品价值
                    maxValue[i][j-1]= Math.max(topValue, thisValue);//更新当前的值
                    //System.out.println("     maxValue"+"["+i+"]"+"["+(j-1)+"]"+maxValue[i][j-1]);
                }*/